package 普里姆Prim算法;

import java.util.Arrays;

public class 普里姆算法 {
	public static void main(String[] args) {
		//普里姆算法，求最小生成树，从点开始
		
		//创建结点数据
		char[] data = new char[] {'A','B','C','D','E','F','G'};
		//结点个数
		int verxs = data.length;
		//邻接矩阵关系，边是否连通，N为大数，表示不连通
		final int N = 65535;
		int[][] weight = new int[][] {
			{N,5,7,N,N,N,2},
			{5,N,N,9,N,N,3},
			{7,N,N,N,8,N,N},
			{N,9,N,N,N,4,N},
			{N,N,8,N,N,5,4},
			{N,N,N,4,5,N,6},
			{2,3,N,N,4,6,N}
		};
		//创建图
		MGraph graph = new MGraph(verxs);
		//创建最小生成树
		MinTree minTree = new MinTree();
		//初始化树
		minTree.createGraph(graph, verxs, data, weight);
		//输出树
		minTree.showGraph(graph);
		//普利姆算法最小生成树
		minTree.prim(graph, 0);
	}
}
/**
 * 最小生成树
 * @author PC
 *
 */
class MinTree{
	
	/**
	 * 创建图的临街矩阵，初始化图，因为现在图还是null，这些参数跟它没关系
	 * @param graph 图对象
	 * @param verxs 图结点个数
	 * @param data 图结点数据
	 * @param weight 图邻接矩阵，图的初始为0
	 */
	public void createGraph(MGraph graph, int verxs, char[] data, int[][] weight) {
		//这些数据，都是参数，需要在外界创建，然后传入，因为图对象是null的，这些参数目前
		//还不是图的属性，下面开始初始化图，将数据，和邻接图画出来（边）
		int i, j;
		for(i = 0; i < verxs; i++) {
			//赋值单个结点数据
			graph.data[i] = data[i]; 
			for(j = 0; j < verxs; j++) {
				//赋值一行的邻接图（边）
				graph.weight[i][j] = weight[i][j];
			}
		}
	}
	
	/**
	 * 普里姆算法最小生成树
	 * @param graph 图
	 * @param v 表示从第几个顶点开始生成，下标
	 */
	public void prim(MGraph graph, int v) {
		//定义一个路径
		char[] m = new char[graph.verxs];
		
		//定义visited数组，表示顶点是否被访问，默认0未访问
		int[] visited = new int[graph.verxs];
		
		//标记当前下标已访问
		visited[v] = 1;
		m[0] = graph.data[v];
		
		//标记开始结点和下一个结点的边（顶点）
		int h1 = -1;
		int h2 = -1;
		//定义一个最小值，代表最短边，默认最大
		int minWeight = 10000;
		//开始循环，因为n个顶点有n-1条边，所以循环条件从1开始，每次确定一条边
		for(int k = 1; k < graph.verxs; k++) {
			//下面开始从已经访问结点开始，一个个找最小的边
			
			//i表示已访问过的顶点，这里只是代指i的意义，因为此时并不能真正看出i是否被访问
			//只能在下面判断时，找出的i是已经访问过的，j同理（i行）
			for(int i = 0; i < graph.verxs; i++) {
				//j表示未访问过的顶点，代指j的意义，此处不能看出是否访问（j列）
				for(int j = 0; j < graph.verxs; j++) {
					//从已访问的顶点第一个开始，向外找最小未访问顶点的边，然后找下一个已访问顶点
					//1.i访问过，j未访问过2.边的权值最小 ;  i相当于当前结点
					if(visited[i] == 1 && visited[j] == 0 && graph.weight[i][j] < minWeight) {
						//找到最小，且未访问过顶点开始替换
						minWeight = graph.weight[i][j];
						//记录两个边，i是以前的顶点，j是新顶点
						h1 = i;
						h2 = j;
					}
				}
			}
			
			//输出
			System.out.println("边["+graph.data[h1]+","+graph.data[h2]+"]"+"权值："+minWeight);
			m[k] = graph.data[h2]; 
			
			//修改已访问
			visited[h2] = 1;
			//修改minWidth为最大
			minWeight = 10000;
		}
		
		System.out.println("路径:"+String.valueOf(m));
	}
	
	/**
	 * 显示邻接图
	 * @param graph
	 */
	public void showGraph(MGraph graph) {
		//输出邻接图
		for(int i = 0; i < graph.verxs; i++) {
			for(int j = 0; j < graph.verxs; j++) {
				System.out.print(graph.weight[i][j] +"\t");
			}
			System.out.println();
		}
	}
	
	
}

/**
 * 图，邻接矩阵
 * @author PC
 *
 */
class MGraph{
	//图结点个数
	int verxs;
	//存放结点数据，有几个结点，就有几个数据，
	char[] data;
	//存放边，邻接矩阵，二维数组，表示x,y是否相连
	int[][] weight;
	
	/**
	 * 初始化图
	 * @param verxs
	 */
	public MGraph(int verxs) {
		//初始化结点个数 
		this.verxs = verxs;
		//初始化结点数据，有几个结点就有几个数据
		data = new char[verxs];
		//初始化邻接矩阵，邻接矩阵等于图的二维化，代表边
		weight = new int[verxs][verxs];
	}
}